For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

4
votes
2answers
54 views

Segments on a family of parallel lines

Let $\{l_i:i\in I\}$ be a family of parallel lines on the plane $\mathbb{R}^2$. Suppose for each $i\in I$ there is a closed segment $s_i\subset l_i$. Moreover, for each triple $i_1,i_2,i_3$ there ...
0
votes
2answers
57 views

In the card game “Projective Set”: Compute the probability that $n$ cards contain a set

In the game of Projective Set, it turns out that any seven cards contain a projective set. For fewer than 7 cards, how can we determine the probability that one or more sets exist (in terms of the ...
0
votes
0answers
32 views

How many boolean formulas are there over n variables?

Suppose our alphabet is $x_1, \ldots, x_n$, $\wedge, \vee$. How many legal boolean formulas can we have? I know it's more than $2^n$ since $$(x_1 \vee x_2) \wedge x_3 \ne x_1 \vee (x_2 \wedge x_3),$$ ...
3
votes
3answers
95 views

Find the number of ways to form 15 teams out of 15 men and 15 women.

In how many ways can 15 teams be formed, each consisting of a man and a woman, from 15 men and 15 women. This looks like the same problem as finding the number of bijective functions from a set $A$ ...
5
votes
1answer
61 views

Expected Value of the Maximum Number of Heads in n Flips

How would one go about finding the expected value of the maximum number of consecutive heads when flipping a coin $n$ times? For small $n$, it seems easy to brute-force it (i.e. when $n = 3$, the ...
4
votes
1answer
92 views

In the card came “Projective Set”, show that 7 cards do always contain a set. [duplicate]

In the game of Projective Set, it turns out that any seven cards contain a projective set. How can one prove this? And for fewer than 7 cards, how can we determine the probability that one or more ...
-2
votes
1answer
76 views

Expected number of numbers chosen. [closed]

Given $n$ persons in a line, if each person chooses randomly any of the integer from $1$ to $n$, given his number is not equal to the integer which the previous and next persons have chosen. For each ...
-1
votes
0answers
26 views

Modular Multiplicative Inverse of a Number

Modular Multiplicative Inverse for a prime M A^(M-1) % M = 1 From Fermat's Little Theorem Hence, A * A^(M-2) % M = 1 Or in other words, A^-1 % M = A^(M-2) % M ...
0
votes
0answers
28 views

Calculating the sum of all pairs

You are given a set of integers. How do you calculate the absolute value sum of all possible pairs? So given {2, -3, 1} $S = |2-3| + |2+1| + |-3+1| = 6$ I realize that there's a pattern here but it ...
0
votes
1answer
21 views

Summation of all possible combinations

I need to get the summation of all triplets produced by (nCr) where r = 3. I've written a program that does this but it takes too long when n is very big.
-2
votes
0answers
50 views

Fastetst method for calculating $\frac{(a+b)!}{a!b!}\bmod{m}$

Is there any faster method for calculating $\frac{(a+b)!}{a!b!}\bmod{m}$? Lucas theorem is also turning out to be slow! $a,b\leq10^9$ and $m=10^6+3$.
-2
votes
2answers
22 views

How many four-digit numbers contain only the digits 1 and 2 and each of them at least once? [closed]

Question: How many four-digit numbers contain only the digits 1 and 2 and each of them at least once? I have tried to do this question by listing all the possible values and have come to answer of ...
0
votes
1answer
34 views

How to calculate $\binom{17}6 21$? [closed]

$\dbinom{17}{6}21$ I understand most of this, where you use $$C(n,r) = \dfrac{n!}{r! (n - r)!}$$ but I am not sure how to calculate with the $21$ and the $17$ choose $6$.
2
votes
1answer
68 views

Pairing Vertices by Edge Color

We have a graph $G$ with an even number of vertices. Every pair of vertices is connected by either a green or red edge. If every vertex is connected to at least one other vertex by a green edge, can ...
2
votes
3answers
86 views

Proving the infinite sum of $1/2^i$ without induction

Prove $$\sum_{i=1}^n \frac{i}{2^i} = 2-\frac{n+2}{2^n} $$ Pretty trivial to do with induction, but as a practice problem for solving recurrences we have to do this only by repeating $\sum_{i=1}^n ...
2
votes
1answer
57 views

Evaluate $\lim_{n\to\infty} \frac{\sum_{r=0}^n\binom{2n}{2r}3^r}{\sum_{r=0}^{n-1}\binom{2n}{2r+1}3^r}$.

Evaluate : $$\lim_{n\to\infty} \frac{\sum_{r=0}^n\binom{2n}{2r}3^r}{\sum_{r=0}^{n-1}\binom{2n}{2r+1}3^r}$$ The answer given is $\sqrt3$. Frankly, have no clue where to begin. I thought of putting ...
3
votes
3answers
56 views

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? [duplicate]

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? $${p^mn \choose p^m} = \frac{(p^mn)!}{p^m!(p^mn-p^m)!} = ...
1
vote
0answers
30 views

Interesting horserace counting problem

So for a horserace with no drawing horses there are n! Results. How many results will there be if the horses can draw?
-2
votes
0answers
20 views

Euler Circuits: little league lesson [closed]

You are in charge of scheduling the baseball games for your town's little league. There are 11 teams in your league. Usually you play 10 games a season, but coaches want to extend that to 13. This ...
0
votes
0answers
34 views

combinatorics,defects on disks

$k$ defects are randomly distributed amongst $n$ computer disks produced by a company AND any number of defects may be found on a disk and each defect is independent of the other defects Let $p(k,n)$ ...
1
vote
0answers
10 views

graph has no bridge iff a spanning subgraph of the graph is the support of a flow

A $\textit{bridge}$ of a graph $G=(V,E)$ (finite graph and we allow loops and multiple edges) is an edge $e$ whose removal disconnects $G$. Let $\mathcal{O}$ be an orientation of the edges of $G$. ...
0
votes
1answer
27 views

Bound the number of different natural numbers that fit as a sum in $n$ as $n$ increases

Let me explain... I have $n$ integers, with $k$ different values where $k \leq n$. If I sum together the integers with same values I will get a set of different values frequencies. Now if I sum ...
4
votes
2answers
67 views

Sum of every row, column and diagonal is equal to 0. Is it possible that none of the numbers is eqaul to zero?

A square with 2015 rows and 2015 columns is filled with integers. The sum of every row is equal to zero, the sum of every column is equal to zero, and sum of the two main diagonals is equal to zero. ...
0
votes
2answers
24 views

Why does $\binom{n}{m}\frac{(n-1)!}{(m-1)!}$ count collections of m ordered lists of n elements?

I'm reading a book on combinatorial proofs and there is one identity there in proof of which it is written that $\binom{n}{m}\frac{(n-1)!}{(m-1)!}$ counts collections of m ordered lists whose disjoint ...
0
votes
1answer
55 views

Sum of Number of non-decreasing sequences [duplicate]

I know that the number of non-decreasing sequences of length $n$ and numbers in the sequence lying in the range $[l,r]$ is given by $$\binom{n+r-l}{n}$$ What is the formula to find the ...
-1
votes
0answers
47 views

No. of paths in a Table [closed]

There is a table of size R×C; R rows and C columns. A sub-rectangle of the table is blocked. We are only able to move right or down. What is the number of paths from the upper-left cell to the ...
0
votes
1answer
19 views

Edge intersections of paths

I am trying to read up on the nonrepetitive graph coloring problem. That's for context, my question can be answered without referring to the problem. I have a graph G, and I am interested in looking ...
1
vote
0answers
158 views

What is the nature and location of maxima of expected log-utility?

Is is possible to describe, and locate efficiently, the maxima of the function below in the parameters $\mathbf{x}$ $$\sum_{i} p_i \log( N + \sum_j x_j[B_j +(A_j-B_j)\delta_{ij} + min(A_j,B_j) ]) ...
0
votes
0answers
42 views

Is there a closed-form expression for the following sum?

Is there a closed-form expression for the following sum: $$\large\sum_{\{n_i\}} \frac{x_i^{n_i}}{\prod_i (i!)^{n_i} n_i!}$$ where the sum runs over all combinations of $\{ n_{i=0,\dots,k} \}$ such ...
2
votes
2answers
119 views

Number of subsets of length 7 [duplicate]

I have the following summation: $$\sum\limits_{k=7}^{n} {k-1\choose 6} $$ and apparently it counts the number of subsets of {1, 2, . . . , n} having size 7. Why is this?
4
votes
2answers
42 views

Constructive Expectation Question

Six balls numbered $1$ through $6$ are in a bin. You randomly draw them out one at a time, without replacement, and put them into boxes numbered $1$ through $6$ (one ball in each box). For each ball ...
0
votes
1answer
65 views

Proving ${n \choose k}^{-1} = (n+1)\int_0^1 x^k(1-x)^{n-k}\mathsf dx$

Title says it all, I've tried to find the indefinite integral of the right side, got some sort of weird series and got stuck: $$\sum_{i=0}^n-k {n-k \choose i}\cdot{(-1)i\over k+1+i}$$
0
votes
1answer
20 views

PIE Problem with divisors

Find the number of positive integers that are divisors of at least one of $10^{10},15^7,18^{11}$. Let $n(A)$ be the number of positive integers that divide $10^{10}$ let $n(B)$ be the number of ...
0
votes
1answer
33 views

Number of ways to distribute n different toys among n children so that any one child gets no toy

Number of ways to distribute n different toys among n children so that any one child gets no toy ? I tried using "star and bar method" and deduced that i need to calculate the number of arrangements ...
2
votes
3answers
39 views

Ways a committee is selectd with at least 2 men and 1 woman.

For this question: A committee of six is to be selected from a group of ten men and 12 women. In how many ways can the committee can be chosen if it has to contain at least two men and one woman? ...
1
vote
1answer
46 views

How to count each numeral of occurrences of digits?

I want to count each numeral(0 through 9) of occurrences of digits in the range $[1, n]$. Note that 101 has two one and one zero. For example, if $n$ equals $11$: ...
-1
votes
0answers
60 views

closed expression for binomial coefficient sum [duplicate]

the above reference is just wrong. It considers a different sum. Having checked with wolfram the right closed form expression is $4^n$. Any ideas how to derive it? I am really unexpierenced how to ...
3
votes
2answers
61 views

A reference for a combinatorial identity

I have come across this identity from study of species. I am not posting my method but I am interested in knowing whether it arises in some other contexts as well. The identity is: $$\sum ...
2
votes
4answers
56 views

What is the probability that an endorsed candidate will be selected to serve on a committee?

$10$ people are being considered to serve as a representative in a committee of $3$ people. Each candidate is equally likely. The President has expressed his support for $2$ of these $10$ candidates. ...
0
votes
2answers
54 views

Counting Distinct matrices

How many distinct (if matrix $M$ is included in count, do not include $PM$ where $P$ is permutation matrix) $3\times 3$ matrices with entries in $\{0,1\}$ are there such that each row is non-zero, ...
1
vote
2answers
30 views

statistics dice problem

If $5$ fair dice are thrown at the same time, how do you find the probability that there are three $1$'s and two $2$'s? The answer says its $5C2 \cdot (1/6)^5$ but I don't understand why.
-2
votes
1answer
46 views

Possible Combinations of a Burger Menu [closed]

If I have a build your own burger menu which has $32$ different options on it $-$ how many combinations are possible?
0
votes
0answers
38 views

Number of combinations for 9 kids to shout 10 number

What is the number of combinations for 9 kids to shout 10 numbers from $1,2,...,10$ such that each kid shouts at least 1 number. The order of the numbers is not important (i.e if a kid shouts "1,10" ...
0
votes
1answer
23 views

Pick 5 Box play PA Lottery odds

I was looking over the PA lottery odds and payout table for the Pick 5 "Quinto" game, specifically for the second row "Boxed - 5 in any order - 5 distinct digits" ...
2
votes
1answer
49 views

indexing all combinations without making list

What is the most efficient way to to find the i'th combination of all combinations without repetition and without first creating all combinations until i. K is fixed (number of elements in each ...
-1
votes
0answers
21 views

Counting five character strings with restrictions [closed]

I have $3$ sets of characters: [A-Z,a-z,0-9] that's $62$ characters in total. I am making string of $5$ characters from these sets. So it's $62^5 = 916132832$ different combinations. How do I count ...
-1
votes
2answers
17 views

Probablity of guessing a Multiple Select Question. [closed]

A Multiple select questions are one in which "One or more" answers are correct. For example: Which of the following people were United States Presidents? A. George Washington B. Abraham Lincoln ...
0
votes
2answers
72 views

Generating function and its closed form

Consider the inequality $x_1 + x_2 + x_3 + x_4 ≤n$ where $x_1,x_2,x_3,x_4,n ≥ 0$ are all integers. Suppose also that $x_2 ≥ 2$, that $x_3$ is a multiple of 4, and $1 ≤ x_4 ≤ 3$. Let $c_n$ be the ...
0
votes
0answers
46 views

Elusive closed form for card permutation problem

Does a closed form formula f(n) exist for the two rightmost columns? The two question marks are meant to be 0. The diagram is a summary of the numerical results from original question: Permutations ...
2
votes
1answer
53 views

Elliptic Function

Let $y$ be the function defined by $$y(\theta)=2sin\frac{\theta}{2}\prod_{k=1}^{\infty}\frac{(1-e^{i\theta}q^k)(1-e^{-i\theta}q^k)}{(1-q^k)^{2}}$$ where $q = e^{2\pi i\tau}$ Show that $y$ has simple ...