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
1answer
137 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 ...
0
votes
0answers
39 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
28 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
2answers
154 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 ...
2
votes
1answer
87 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
92 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
60 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
64 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
40 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?
0
votes
0answers
48 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
12 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
31 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
315 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
25 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
99 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 ...
0
votes
1answer
23 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 ...
0
votes
0answers
55 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
160 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
83 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
89 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
33 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
185 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
218 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
80 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$: ...
3
votes
2answers
67 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
131 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
79 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
38 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.
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
157 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
97 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 ...
0
votes
2answers
94 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 ...
1
vote
0answers
83 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
116 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 ...
2
votes
2answers
107 views

How many ways can we split a group of $n$ elements into groups of different sizes such that each group contains more than $1$element

let's assume $p[n]$ is the name of this partitioning method Let's see some examples: $n=3$: all possibilities are: $[(3,0),(2,1),(1,1,1)]$ all cases don't meet the condition $minSize > 1$ so ...
1
vote
2answers
45 views

Proof that all n-length subsets have been generated from a set.

I have a function in a computer program that generates integer subsets within an integer set. The function takes an set of sequential numbers and finds all the possible subsets of a given length. The ...
4
votes
2answers
110 views

Ways to form a committee - why is this approach incorrect?

I have the following question: If there are 7 women and 9 men, how many ways are there to select a committee of 5 members if at least 1 man and 1 woman must be on the committee? I have found the ...
-3
votes
2answers
207 views

Combinatorial homework problem. [closed]

This is for homework so I don't want any solutions. Just some guidance. Problem: Alice has $10$ balls (all different). First, she splits them into two piles; then she picks one of the piles with at ...
2
votes
2answers
80 views

20 types of candy available. How many ways can you put exactly 2 types of candy in a box with 10 spaces?

I think first you find the number of ways to choose your $2$ types via combination, and then putting them in the box is just with replacement, $n^k$. This will also count where all $10$ are the same ...
2
votes
3answers
156 views

Calculate number of (four-letter) strings that contain exactly two matching characters (s)

The following problem refers to strings in A, B, ..., Z. Question: How many four-letter strings are there that contain exactly two S's? I used the formula in this answer to come up with the ...
0
votes
0answers
53 views

combinatorial proof of Vandermonde's Identity [duplicate]

So I can not figure out the combinatorial proof for Vandermonde's Identity for the example $\sum_{i=0}^k \binom {k} {i}^2 = \binom {2k} {k}$ Any help would be appreciated. Figured it out, thanks :)
3
votes
0answers
44 views

Forming the graph $G$ from elements of the cut and cycle space, using a weird hint

I'm working through a set of lecture notes on my own, and since there is no class, there are no immediate faculty members available to ask questions to. I've managed to finish most exercises quite ...
4
votes
1answer
186 views

Lengths of the shortest “simple” equation, that use only the number '1', equal to a given natural numbers.

Is there a formula, for determining the length of the shortest formula, that uses only the number '1', parenthesis, and the hyperoperations $\{\{+, - \}, \{\times, / \}, \{\text{^}, \log_N,\text{nth ...
2
votes
1answer
64 views

Does anybody spot anything familiar in this integer sequence?

$0,3,9,21,40,67,106,154,220,298,395,510,644,\dots$ These are the maxima of the distances between permutations of length $n$ up to $n=13$ according to a modified version of Spearman's footrule number ...
1
vote
1answer
38 views

In how many ways can 3 monitors be oriented and placed on a desk?

There are $3$ distinguishable monitors and each monitor can be oriented in $4$ unique ways. In how many ways can you arrange them on a desk? ($3$ positions in total) My attempt: There are $3!$ ways ...
0
votes
1answer
27 views

Is there a definitive formula for this combination?

To help Lavanya learn all about binary numbers and binary sequences, her father has bought her a collection of square tiles, each of which has either a 0 or a 1 written on it. Her brother Nikhil has ...
0
votes
1answer
59 views

Placing identical balls into identical boxes

If $12$ identical balls are to be placed in $3$ identical boxes, then the probability that one of the boxes contains exactly $3$ balls is? This question has already been posed on this site, but in ...
0
votes
0answers
100 views

Counting all permutations(repeating) with no adjacent elements equal and m majority elements.

Counting all permutations(repeating) of 1 to n which have size n. 1. with no adjacent elements equal, and 2. m majority elements(A element is majority element when it appears max number of times in ...
2
votes
1answer
65 views

Number of permutations with subset distance constraint

The problem is to calculate the number of all unique permutations of a string with repetitions. There is also a constraint for one subset elements to be spaced from each other. Typical input data is ...
2
votes
1answer
38 views

There are n balls and m colors, calculate the ways that color 1 appear most

Also, color 1 can be as many as others. for example: there 2 balls and 3 colors, we can color like that: 1 1, 1 2, 1 3, 2 1, 2 2, 2 3, 3 1, 3 2, 3 3 and 1 1, 1 2, 1 3, 2 1, 3 1 are the valid ...